home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung 2 / Power-Programmierung CD 2 (Tewi)(1994).iso / c / library / dos / diverses / leda / incl / bb_tree.h < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  5.8 KB  |  251 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  bb_tree.h
  7. +
  8. +
  9. +  Copyright (c) 1991  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17.  
  18. #ifndef BBTREEH
  19. #define BBTREEH
  20.  
  21. //--------------------------------------------------------------------
  22. //  
  23. //  BB[alpha] Trees
  24. //
  25. //  Michael Wenzel   (1989)
  26. //
  27. // Implementation follows
  28. // Kurt Mehlhorn: Data Structures and Algorithms 1, section III.5.1
  29. //
  30. // Aenderungen:
  31. //   - virtuelle compare-Funktion   (M. Wenzel, Nov. 1989)
  32. //--------------------------------------------------------------------
  33.  
  34.  
  35. #include <LEDA/b_stack.h>
  36.  
  37.  
  38. // -----------------------------------------------------
  39. // declarations and definitions
  40. // -------------------------------------------------------
  41.  
  42. const int BSTACKSIZE = 32 ; // according to tree.size and alpha
  43.  
  44. const float SQRT1_2 = 0.70710678;
  45.  
  46. class bb_node;
  47. class bb_tree;
  48.  
  49. typedef bb_node* bb_item;
  50.  
  51. typedef bb_node* bb_tree_item;
  52.  
  53. declare(b_stack,bb_item);
  54. typedef b_stack(bb_item) bb_tree_stack;
  55.  
  56.  
  57. typedef void (*DRAW_BB_NODE_FCT)(double,double,void*);
  58. typedef void (*DRAW_BB_EDGE_FCT)(double,double,double,double);
  59.  
  60. class bb_node {
  61.  
  62.   ent ke;
  63.   ent inf;
  64.   int gr;
  65.   bb_item sohn[2];
  66.  
  67.   friend class bb_tree;
  68.   friend class range_tree;
  69.   friend class Segment_Tree;
  70.   friend class seg_node_tree;
  71.  
  72. public:
  73.  
  74.   ent key()           { return ke; }
  75.   ent info()          { return inf; }
  76.  
  77.   int blatt()         { return (gr==1); }
  78.   int groesse()       { return gr; }
  79.  
  80.   float bal()
  81.     { if (blatt()) return 0.5 ;
  82.       else return float(float(sohn[0]->groesse())/float(gr));
  83.         }
  84.  
  85.   bb_node(ent k=0,ent i=0,int leaf=0,bb_item ls=0,bb_item rs=0)
  86.     { ke = k;
  87.       inf = i;
  88.       sohn[0] = ls;
  89.       sohn[1] = rs;
  90.       if (leaf==0)
  91.     gr=1;
  92.       else gr = ls->groesse()+rs->groesse();
  93.     }
  94.  
  95.   bb_node(bb_item p)
  96.     { 
  97.       ke = p->key();
  98.       inf = p->info();
  99.       gr = p->groesse();
  100.       sohn[0] = p->sohn[0];
  101.       sohn[1] = p->sohn[1];
  102.     }
  103.       
  104.   OPERATOR_NEW(5)
  105.   OPERATOR_DEL(5)
  106.  
  107. }; 
  108.  
  109.  
  110.  
  111. class bb_tree {
  112.  
  113.   bb_item root;
  114.   bb_item first;
  115.   bb_item iterator;
  116.   int   anzahl; 
  117.   float alpha;
  118.   float d;
  119.   bb_tree_stack st;
  120.  
  121.   friend class bb_node;
  122.   friend class range_tree;
  123.   friend class seg_node_tree;
  124.   friend class Segment_Tree;
  125.  
  126.   int   blatt(bb_item it)
  127.     { return (it) ? it->blatt() : 0; }
  128.  
  129.   void  lrot(bb_item , bb_item ); 
  130.   void  rrot(bb_item , bb_item ); 
  131.   void  ldrot(bb_item , bb_item ); 
  132.   void  rdrot(bb_item , bb_item ); 
  133.  
  134.   void  deltree(bb_item);
  135.   bb_item copytree(bb_item , bb_item , bb_item& );
  136.   bb_item search(ent);
  137.   bb_item sinsert(ent , ent );
  138.   bb_item sdel(ent );
  139.  
  140. public:
  141.  
  142.   virtual int cmp(ent& x,ent& y) { return int(x)-int(y); }
  143.   virtual void clear_key(ent& x) const { Clear(x); }
  144.   virtual void clear_inf(ent& x) const { Clear(x); }
  145.  
  146.   virtual void copy_key(ent& x)  const { Copy(x);  }
  147.   virtual void copy_inf(ent& x)  const { Copy(x);  }
  148.  
  149.   ent     key(bb_item it)  const   { return it->ke;  }
  150.   ent&    info(bb_item it)         { return it->inf; }
  151.   ent     inf(bb_item it)  const   { return it->inf; }
  152.   ent     translate(ent y);
  153.  
  154.   bb_item insert(ent ,ent );
  155.   bb_item change_obj(ent ,ent );
  156.   bb_item change_inf(bb_item it,ent y)
  157.           { if (it)  
  158.         { it->inf = y;
  159.           return it; }
  160.         else return 0;
  161.               }
  162.   
  163.  
  164.   bb_item del(ent );
  165.  
  166.  
  167.   void del_item(bb_item it) { if (it) del(it->key()); }
  168.   void del_min() { if (first) del(first->key()); } 
  169.   void decrease_key(bb_item p, ent k) { ent i = p->info(); 
  170.                                         //copy_inf(i);
  171.                                         del(p->key());
  172.                                         insert(k,i);
  173.                                         //clear_inf(i);
  174.                                        }
  175.  
  176.   bb_item locate(ent );
  177.   bb_item located(ent );
  178.   bb_item lookup(ent );
  179.  
  180.   bb_item cyclic_succ(bb_item it)  const
  181.         { return it ? it->sohn[1] : 0 ; }
  182.   bb_item cyclic_pred(bb_item it)  const
  183.       { return it ? it->sohn[0] : 0 ; }
  184.   bb_item succ(bb_item it) const
  185.           { return ( it && it->sohn[1] != first ) ? it->sohn[1] : 0 ; }
  186.   bb_item pred(bb_item it) const
  187.           { return ( it && it != first ) ? it->sohn[0] : 0 ; }
  188.  
  189.   bb_item ord(int k);
  190.   bb_item min()       const    { return (first) ? first : 0; }
  191.   bb_item find_min()  const    { return (first) ? first : 0; }
  192.   bb_item max()       const    { return (first) ? first->sohn[0] : 0 ; }
  193.  
  194.   bb_item first_item() const         { return (first) ? first : 0; }
  195.   bb_item next_item(bb_item x) const { return succ(x); }
  196.  
  197.   bb_item move_iterator() ;
  198.  
  199.   int current_item(bb_item& x) 
  200.      { if (!iterator) return 0;
  201.        else { x = iterator; return 1; }
  202.      }
  203.  
  204.  
  205.   void init_iterator()          { iterator = 0; }
  206.   void  lbreak()                { iterator = 0; }
  207.  
  208.  
  209.   void  clear();
  210.   int   size()    const        { return anzahl; }
  211.   int   empty()   const        { return (anzahl==0) ? true : false; }
  212.  
  213.   int   member(ent );
  214.   bb_tree& operator=(bb_tree& w);
  215.  
  216.   void  set_alpha(float a) 
  217.         { if (anzahl>=3)
  218.              error_handler(4,"aenderung von alpha nicht erlaubt");
  219.           if ((a<0.25) || (a>1-SQRT1_2))
  220.              error_handler(3,"alpha not in range");
  221.           alpha=a;
  222.           d = 1/(2-alpha) ;
  223.         }
  224.  
  225.   float get_alpha() { return alpha; }
  226.  
  227.   bb_tree() : st(BSTACKSIZE)
  228.   { 
  229.     root = first = iterator = 0;
  230.     anzahl = 0;
  231.     alpha=0.28;
  232.     d=1/(2-alpha);
  233.   }
  234.  
  235.   bb_tree(float);
  236.   bb_tree(bb_tree&);
  237.  
  238.   ~bb_tree()  { clear(); }
  239.  
  240.  
  241.   void draw(DRAW_BB_NODE_FCT, DRAW_BB_EDGE_FCT, bb_node*,
  242.           double, double, double, double, double);
  243.  
  244.   void draw(DRAW_BB_NODE_FCT, DRAW_BB_EDGE_FCT, 
  245.           double, double, double, double);
  246.  
  247. };
  248.  
  249.  
  250. #endif
  251.